package sort;

public class HeapSortInPlace {
	private static int[] array;
	private static int size;
	
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();

		HeapSortInPlace.array = list;
		HeapSortInPlace.size = array.length;
		
		for(int i=list.length>>1; i>=0; i--) heapify(i);
		while(size>1) {
			swap(0, --size);
			heapify(0);
		}

		return System.currentTimeMillis()-startTime;
	}
	
	private static void heapify(int i) {
		int largest = (i<<1)+1;

		if(largest>=size) return;
		if(largest+1<size && array[largest+1] > array[largest]) largest++;
		
		if(array[largest] > array[i]){
			swap(i, largest);
			heapify(largest);
		}
	}

	private static void swap(int index1, int index2) {
		int tmp = array[index1];
		array[index1] = array[index2];
		array[index2] = tmp;        
    }
}